// Zadanie: Odleglosc edycyjna
// Autor: Marcin Milewski
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#include <stdio.h>
#include <sys/types.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>

#include <cutil_inline.h>

const int MAX_L = 16;  // Maksymalna dlugosc slowa (łącznie z 0 na końcu napisu)

void checkCUDAError(const char *msg) {
    cudaError_t err = cudaGetLastError();
    if( cudaSuccess != err) {
        fprintf(stdout, "Cuda error: %s: %s.\n", msg, 
                                  cudaGetErrorString( err) );
        exit(EXIT_FAILURE);
    }                         
}

char* dCharDict;   // slownik na karcie (kolejne slowa oddzielone sa zerem -- \0


//========================================================================
// Funkcja testowa OE_CPU() do porównywania na CPU 
//
// Tablice tymczasowe do uzycia w liczeniu odleglosci edycyjnej na CPU 
int gt1C[MAX_L];
int gt2C[MAX_L];

__host__ __device__ inline int minimum(const int a,const int b,const int c){
   return a<b? (c<a?c:a): (c<b?c:b);
}

// Odległosc edycyjna Levenshtein'a

const char* last_word = "\0";
int last_len = 0;
inline int first_mismatch(const char *a,const int aN, const char *b,const int bN) {
    for (int i=0; i <= aN && i <= bN; ++i) {
        if (a[i]!=b[i])
            return i;
    }
    return aN<bN?aN:bN; // min(aN,bN)
}

int best_so_far = 999888777;
// int usage_ile=0;
// double usage_sum=0;
inline int OE_CPU_im(const char *a,const int aN, const char *b,const int bN) {
   int *d1 = gt1C;
   int *d2 = gt2C;

   for (int j=0; j<=bN; j++)
       d1[j]=j;
   
   // int fm = first_mismatch(last_word, strlen(last_word), b, bN);
   // std::cout << float(fm)/bN << "\t" << fm << "\t" << bN << std::endl;
   // usage_ile++;
   // usage_sum+=double(fm)/bN;

   last_word = b;
   last_len = bN;
       
   bool any_lower_than_best = false;
   for (int i=1; i<=aN; i++) {
      d2[0] = i;
      any_lower_than_best = false;
      for (int j=1;j<=bN;j++) {
         d2[j] = minimum(d1[j  ] + 1,                        // deletion
                         d2[j-1] + 1,                        // insertion
                         d1[j-1] + ((a[i-1]==b[j-1])? 0:1)); // substitution
         if (d2[j] <= best_so_far) {
             any_lower_than_best = true;
         }
      }
      d1 = (d1==gt1C)? gt2C:gt1C; // table exchange 1<>2
      d2 = (d2==gt2C)? gt1C:gt2C; // table exchange 1<>2
      if (any_lower_than_best == false)
          break;
   }

   return d1[bN];
}

inline int OE_CPU(const char *a,const int aN, const char *b,const int bN) {
   int *d1 = gt1C;
   int *d2 = gt2C;

   for (int j=0;j<=bN;j++) d1[j]=j;

   for (int i=1;i<=aN;i++) {
      d2[0] = i;
      for (int j=1;j<=bN;j++) {
         d2[j] = minimum(d1[j  ] + 1,                        // deletion
                         d2[j-1] + 1,                        // insertion
                         d1[j-1] + ((a[i-1]==b[j-1])? 0:1)); // substitution
      }
      d1 = (d1==gt1C)? gt2C:gt1C; // table exchange 1<>2
      d2 = (d2==gt2C)? gt1C:gt2C; // table exchange 1<>2
   }

   return d1[bN];
}


__device__ int OE_GPU(const char *a, const int aN, const char *b, const int bN) {
  int aaagt1C[MAX_L];
  int aaagt2C[MAX_L];

   int *d1 = aaagt1C;
   int *d2 = aaagt2C;

   for (int j=0;j<=bN;j++) d1[j]=j;

   for (int i=1;i<=aN;i++) {
      d2[0] = i;
      for (int j=1;j<=bN;j++) {
         d2[j] = minimum(d1[j  ] + 1,                        // deletion
                         d2[j-1] + 1,                        // insertion
                         d1[j-1] + ((a[i-1]==b[j-1])? 0:1)); // substitution
      }
      d1 = (d1==aaagt1C)? aaagt2C:aaagt1C; // table exchange 1<>2
      d2 = (d2==aaagt2C)? aaagt1C:aaagt2C; // table exchange 1<>2
   }

   return d1[bN];
}


__device__ int stringlen(char* s) {
  int length = 0;
  while(*s++ !='\0')
    length++;
  return length;
}


/* 
 * result          - wynik (pary: odleglosc edycyjna, offset w slowniku)
 * dDictionary     - slownik na karcie
 * dWord           - slowo do przetworzenia (w pamieci karty)
 * word_len        - dlugosc slowa dWord
 * dict_entry_size - rozmiar wejscia w slowniku (dlugosc najdluzszczego slowa + 1 (na '\0')
 * dict_len        - ilosc slow w slowniku
 */
__global__ void Kernel(int* result, char* dDictionary, char* dWord, int word_len, int dict_entry_size, int dict_len) {

  // pozycja slowa (do sprawdzenia) w slowniku
  int pos = 0;

  pos
    =  blockDim.x * blockIdx.x + threadIdx.x 
    + (blockDim.y * blockIdx.y + threadIdx.y) * blockDim.x * gridDim.x;

  if (pos >= 2*800000 || pos >= dict_len)
    return;

  int k = 2 * pos;  // indeks na zapisanie wyniku (wartosc lcs; offset slowa)

  char* slowo_ze_slownika = &dDictionary[dict_entry_size * pos];
  result[k] = OE_GPU(dWord, word_len, slowo_ze_slownika , stringlen(slowo_ze_slownika));
  result[k+1] = pos;   // numer slowa w slowniku

  if (result[k] < 0 ) {
    result[k] = -8;
  }
  // int max_word_len = 0;
  // for (int i=0; i<dict_len; ++i) {
  //   int len = stringlen(&dDictionary[dict_entry_size*i]);
  //   if (len > max_word_len ) {
  //     max_word_len = len;
  //   }
  // }
  // result[0] = max_word_len;
}


void GPULeven(int* result, char* iword, int dict_entry_size, int dict_len) {
  // wyslij slowo na karte
  printf("    wysylanie slowa na karte\n");
  int iword_len = strlen(iword);
  char* dWord;
  cudaMalloc(&dWord, iword_len);
  cudaMemcpy(dWord, iword, iword_len, cudaMemcpyHostToDevice);

  // utworz na karcie pola do wstawienia wyniku
  printf("    tworzenie pamieci na wynik na karcie\n");
  int dResult_size = 2 * 800000 * sizeof(int);
  int *dResult;
  cudaMalloc(&dResult, dResult_size);
  cudaMemcpy(dResult, result, dResult_size, cudaMemcpyHostToDevice);  // wypelnij karte domyslna wartoscia


  // odpal jadro
  printf("    uruchamianie jadra\n");
  dim3 dimGrid (256, 32);
  dim3 dimBlock(128);
  
  Kernel<<<dimGrid, dimBlock>>>(dResult, dCharDict, dWord, iword_len, dict_entry_size, dict_len);
  printf("    koniec jadra\n");

  // skopiuj wyniki z karty do cpu
  printf("    kopiowanie wynikow\n");
  cudaMemcpy(result, dResult, dResult_size, cudaMemcpyDeviceToHost);
  printf("    zwalnianie pamieci dResult\n");
  cudaFree(dResult);
}


//========================================================================
// Bardzo prymitywny test funkcji OE_CPU i wzorzec jak i czym mierzyć czas
// 
int main(int argc, char** argv) {
  // -------------------------------------------------------------------- 
  // Zaladuj slownik
  
  int slow_w_pliku = 512*512*3; //795875;
  slow_w_pliku     = 795875;

  typedef std::vector<std::string> Slownik;
  std::ifstream infile(argv[1]);
  Slownik vSlowa(slow_w_pliku);
  {
    for (int i=0; i < slow_w_pliku; ++i) {
      infile >> vSlowa.at(i);
    }
  }

  int max_word_len=0;
  //   int x=0;
  for (Slownik::const_iterator i=vSlowa.begin(); i!=vSlowa.end(); ++i) {
    if ((*i).size() > max_word_len) {
      max_word_len = (*i).size();
    }
    // std::cout << "input  " << x++ << " \t" << *i << std::endl;
  }
  std::cout << "długość najdłuższego ciągu w słowniku: " << max_word_len << std::endl;

  // skopiuj slownik na karte
  std::cout << "Kopiowanie slowanika na karte" << std::endl;
  int charDict_size = slow_w_pliku * (max_word_len+1);
  char* charDict = (char*)calloc(charDict_size, 1);
  std::cout << "  Skopiuje " << slow_w_pliku << " slow" << std::endl;
  std::cout << "  Wypelnianie pamieci CPU" << std::endl;
  for (int i=0; i < slow_w_pliku; ++i) {
    int offset_in_dict = (max_word_len+1) * i;
    for (int c=0; c < vSlowa.at(i).length(); ++c) {
      charDict[offset_in_dict+c] = vSlowa.at(i).at(c);
    }
  }
  std::cout << "  Kopiowanie na karte" << std::endl;
  //   char* dCharDict;  // zmienna globalna
  cudaMalloc(&dCharDict, charDict_size);
  cudaMemcpy(dCharDict, charDict, charDict_size, cudaMemcpyHostToDevice);
  std::cout << "  Kopiowanie zakonczone" << std::endl;

  // podglad slownika w pamieci CPU
  // for (int i=0; i<slow_w_pliku *(max_word_len+1); ++i) {
  //   if (charDict[i]==0)
  //     std::cout << "*";
  //   else
  //     std::cout << charDict[i];
  // }

  // -------------------------------------------------------------------- 
  // -GPU:--------------------------------------------------------------- 
  // -------------------------------------------------------------------- 
  // Slownik możemy przeslać na GPU tutaj: tego nie liczymy do czasu 
  // Tylko słownik, nie słowa !
  // ... 

  // Testowanie na wszystkich slowach ktore sa kolejnymu argumentami 
  // wywolania programu (argv, poza pierwszym: plik slownika) GPU/CPU
  // -------------------------------------------------------------------- 
  //   unsigned int gpu_timer = 0;
  // cutilCheckError( cutCreateTimer( &timer));
  // cutilCheckError( cutStartTimer(   timer));

  // GPU load run get 
  // ...
  printf("Uruchamianie testow na wszystkich slowach\n");
  for (int i=2; i < argc; ++i) {
    printf("\n");
    {
      char* input_word  = argv[i];
      printf(" testowane slowo: %s", input_word);
      int gpu_len = 88888;
      int gpu_offset = 88888;
      int* result = (int*)malloc(2 * 800000 * sizeof(int)); //2 * slow_w_pliku * sizeof(int));
      for (int i=0; i < 2 * 800000; ++i) {
	result[i] = 88888;
      }

      unsigned int gpu_timer = 0;
      cutilCheckError(cutCreateTimer(&gpu_timer));  cutilCheckError(cutStartTimer(gpu_timer));
      printf("  GPULeven... start\n");
      GPULeven(result, input_word, max_word_len+1, slow_w_pliku);
      printf("  GPULeven... done\n");
      checkCUDAError("kernel invocation");

      // znajdz najlepsze rozwiązanie
      printf("  Obliczanie najlepszego rozwiazania\n");

      int ile_888 = 0;
      for (int d=0; d<slow_w_pliku; ++d) {
	if (result[d*2] > 20) {
	  ile_888++;
	}
      }
      printf("ERROR: #bad values: %d\n", ile_888);

      int ile_ok = 0;
      for (int d=0; d<800000; ++d) {
	if (0<= result[d*2] && result[d*2] <= 20) {
	  ile_ok++;
	}
      }
      printf("ERROR: #ok values: %d\n", ile_ok);

      for (int i=0; i < slow_w_pliku; ++i) {

	// printf("TRACE: %d %d (%d)\n", result[i * 2], result[i * 2 + 1], i);

	// if (result[i * 2 + 1] != i) {
	//   printf("ERROR: %d %d (%d)\n", result[i * 2], result[i * 2 + 1], i);
	//   break;
	// }
	
	if (result[i*2] >=0 && result[i*2] < gpu_len) {
	  gpu_len    = result[i * 2];
	  gpu_offset = result[i * 2 + 1];
	}

	if (result[i*2] > 888) {
	  printf("ERROR: first bad value: %d\n", i);
	  break;
	}

	// if (result[i*2] == 0) {
	//   printf("i: %d\n", i);
	//   break;
	// }

      }
      printf("  Rozwiazanie:\n");
      printf("    len:    %5d\n", gpu_len);
      printf("    offset: %5d\n", gpu_offset);
      printf("    slowo:   %s\n", vSlowa.at(gpu_offset).c_str());

      // cutilCheckError(cutStopTimer(gpu_timer)); gpu_elapsedTimeInMs = cutGetTimerValue(gpu_timer);

      printf( "GPU---- time: %10.2f ms ------- ", cutGetTimerValue( gpu_timer));
      cutilCheckError( cutDeleteTimer( gpu_timer));

      // GPU rezultaty wypisać tu:
      // ...
      // printf("Len: %d  Offset: %d\n", gpu_len, gpu_offset);
      printf("Wzorzec:%16s Znaleziony:%16s (odleglosc=%3d)\n",
	     input_word,   vSlowa.at(gpu_offset).c_str(), gpu_len);

      free(result);
    }

    // -------------------------------------------------------------------- 
    // -CPU:--------------------------------------------------------------- 
    // -------------------------------------------------------------------- 
    // cutilCheckError( cutCreateTimer( &timer));
    // cutilCheckError( cutStartTimer( timer));
    

    // CPU run
    // ...

    float cpu_time = 88888;;
    {
      clock_t start = clock() / (CLOCKS_PER_SEC / 1000);
      const char *s = argv[i];
      int minlCPU=999999, miniCPU;
      for (int i=0; i < vSlowa.size(); i++) {
	const char *d = vSlowa.at(i).c_str(); //pSlowa+MAX_L*i;
	int   l = OE_CPU(s,  strlen(s),    d,  strlen(d));
	// std::cout <<  l << "\t" << vSlowa.at(i) << std::endl;
	if (l < minlCPU) {
	  minlCPU=l;
	  miniCPU=i;
	}
      }
      clock_t end = clock() / (CLOCKS_PER_SEC / 1000);
      cpu_time = (float)(int)(end-start);
      printf( "CPU-ORG time: %10.2f ms ------- ", cpu_time);
      printf("Wzorzec:%16s Znaleziony:%16s (odleglosc=%3d)\n",
	     s,      vSlowa.at(miniCPU).c_str(), minlCPU);
    }

    float cpu_max_time = 8888;
    {
      best_so_far = 999888777;
      clock_t start = clock() / (CLOCKS_PER_SEC / 1000);
      const char *s = argv[i];
      int minlCPU=999999, miniCPU;
      for (int i=0; i < vSlowa.size(); i++) {
	const char *d = vSlowa.at(i).c_str(); //pSlowa+MAX_L*i;
	int   l = OE_CPU_im(s,  strlen(s),    d,  strlen(d));
	// std::cout <<  l << "\t" << vSlowa.at(i) << std::endl;
	if (l < minlCPU) {
	  minlCPU=l;
	  miniCPU=i;
	  best_so_far = l;
	}
	if (minlCPU == 0)
	  break;
      }
      clock_t end = clock() / (CLOCKS_PER_SEC / 1000);
      cpu_max_time = (float)(int)(end-start);
      printf( "CPU-max time: %10.2f ms %7.2f ", cpu_max_time, cpu_time/cpu_max_time);
      printf("Wzorzec:%16s Znaleziony:%16s (odleglosc=%3d)\n",
	     s,      vSlowa.at(miniCPU).c_str(), minlCPU);
    }
  }
   
  // std::cout << "Srednia wykorzystalnosci: " << usage_sum/usage_ile << std::endl;

  // char *s=argv[2];  // na poczatek tylko pierwsze slowo <- testowac wszystkie
  // int minlCPU=999999, miniCPU;
  // for (int i=0; i<nSlow; i++) {
  //    char *d = pSlowa+MAX_L*i;
  //    int   l = OE_CPU(s,  strlen(s),    d,  strlen(d));
  //    if (l<minlCPU) {
  //        minlCPU=l;
  //        miniCPU=i;
  //    }
  // }
  // clock_t end = clock() / (CLOCKS_PER_SEC / 1000);
  // printf( "CPU time: %2.6f (ms)\n", (float)(int)(end-start));

  // printf( "CPU time: %2.6f (ms)\n", cutGetTimerValue( timer));
  // cutilCheckError( cutDeleteTimer( timer));

  // CPU rezultaty wypisać tu:
  // printf("Wzorzec:%16s Znaleziony:%16s (odleglosc=%3d)\n",
  //                  s,      pSlowa+MAX_L*miniCPU, minlCPU);

  // -------------------------------------------------------------------- 
  return 0;
}
